package Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class test {





    public int longestOnes(int[] nums, int k) {
        int ret=0;
        for(int left=0,right=0,zero=0;right<nums.length;right++){
            if(nums[right]==0){
                zero++;
            }
            while(zero>k){
                if(nums[left++]==0){
                    zero--;
                }
            }
            ret=Math.max(ret,right-left+1);
        }
        return ret;
    }

    public int lengthOfLongestSubstring(String s) {
        char[]c=s.toCharArray();
        int left=0,right=0,len=0;
        int []hash=new int[128];
        while(right<c.length){
            hash[c[right]]++;
            while(hash[c[right]]>1){
                hash[c[left++]]--;
            }
            len=Math.max(len,right-left+1);
            right++;
        }
        return len;
    }



    public static void main3(String[] args) {
        int []nums={2,3,1,2,4,3};
        System.out.println(minSubArrayLen(7, nums));
        int []nums1={1,4,4};
        System.out.println(minSubArrayLen(2, nums1));
    }

    public static int minSubArrayLen(int target, int[] nums) {
        int len=Integer.MAX_VALUE;
        int left=0;
        int right=0;
        int sum=0;
        for (; right <nums.length; right++) {

                sum+=nums[right];
            while (sum>=target) {
                len = Math.min(len, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }
        return len;
    }


    public static void main2(String[] args) {
        int []nums={2,2,2,2,2};
        int []num1={1,0,-1,0,-2,2};
        System.out.println(fourSum(num1, 0).toString());
    }

    public static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
        List<List<Integer>>res=new ArrayList<>();
        for (int i = 0; i <nums.length-3 ;) {
         long t1=target-nums[i];
            for (int j = i+1; j <nums.length-2 ;) {
                long t2=t1-nums[j];
                int left=j+1;
                int right= nums.length-1;
                while (left<right){
                    int sum=nums[left]+nums[right];
                    if (sum>t2){
                        right--;
                    }else if(sum<t2){
                        left++;
                    }else {
                        List<Integer>list=new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(nums[left]);
                        list.add(nums[right]);
                        res.add(list);
                        left++;
                        right--;
                        while (nums[left]==nums[left-1]&&left<right){
                            left++;
                        }
                        while (nums[right]==nums[right+1]&&left<right){
                            right--;
                        }
                    }

                }
                j++;
                while(nums[j]==nums[j-1]&&j<nums.length-2){
                    j++;
                }
            }
i++;
            while (nums[i]==nums[i-1]&&i< nums.length-3){
                i++;
            }

        }
        return res;
    }


    public static void main1(String[] args) {
        int []nums={1,-1,-1,0};
        System.out.println(threeSum(nums).toString());
    }

    public static List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>>res=new ArrayList<>();
        for (int i = 0; i < nums.length -2;) {
            int left=i+1;
            int right= nums.length-1;
            int tager=-nums[i];
            if(nums[i]>0){
                return res;
            }
            while(left<right){
           int sum=nums[left]+nums[right];
                if(sum>tager){
                    right--;
                } else if (sum<tager) {
                    left++;
                }else {
              List<Integer>list=new ArrayList<>();
                    list.add(nums[i]);
                    list.add(nums[left]);
                    list.add(nums[right]);
                    res.add(list);
                    left++;
                    right--;
                    while(nums[left]==nums[left-1]&&left<right){
                        left++;
                    }
                    while(nums[right]==nums[right+1]&&left<right){
                        right--;
                    }
                }
            }                i++;
            while(nums[i]==nums[i-1]&&i< nums.length-2){
                i++;
            }
        }
        return res;
    }

}
